package sortieren;

public class QuickSort extends GetSwapSorter{
  public QuickSort(){ super(2); }

  @SuppressWarnings("empty-statement")      // innerste while-Schleifen sind leer
  void quicksort(int links, int rechts){
    if(links<rechts){
      int pivot=get(links);                 // wird oft gebraucht
      int li=links, re=rechts;              // Arbeitskopieen der Grenzen
      mark(links, 2); mark(rechts-1, 2);    // Kosmetik: markiere die Grenzen
      while(li<re){
        while(get(--re)>pivot);             // Diese beiden Schleifen sind leer;
        while((li<re) && (get(++li)<pivot));// Schleifenkopf schiebt Grenzen.
        swap(li, re);
      }
      if(links!=re) swap(links, re);        // Pivotwert an die richtige Stelle
      mark(links,0,0); mark(rechts-1,0,0);  // Kosmetik: entmarkiere die Grenzen
      quicksort(links, re);
      quicksort(re+1, rechts);
    }
  }

  @Override
  public void sort(){
    quicksort(0, length());
  }
}
